package Z.dailyExercise._0110;

import Z.dailyExercise._1223._13_罗马数字转整数;

public class _167_两数之和II输入有序数组 {
    public static void main(String[] args) {
        _167_两数之和II输入有序数组 test = new _167_两数之和II输入有序数组();
        test.twoSum(new int[]{2,7,11,15},9);
    }
    /**
     * 自解：寻找一个子区间进行求解,在子区间用双指针---
     * 子区间：最大值小于等于target
     * ==问题转化 找小于等于target的最大数值
     * ==麻烦，因为递归寻找时不好找
     *
     *
     * 他题解：1-二分查找（固定一个数值 在他的右边寻找target-num的数值）O(nlogN)
     * 2-双指针：就用下面的过程 O(n)-better
     * @param numbers
     * @param target
     * @return
     */

    public int[] twoSum(int[] numbers, int target) {


        int rightIndex = helper(numbers,target,0, numbers.length-1);

        if (rightIndex == -1){
            return new int[]{-1, -1};
        }
        /**
         * 使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。假设 \text{numbers}[i]+\text{numbers}[j]=\text{target}numbers[i]+numbers[j]=target 是唯一解，其中 0 \leq i<j \leq \text{numbers.length}-10≤i<j≤numbers.length−1。初始时两个指针分别指向下标 00 和下标 \text{numbers.length}-1numbers.length−1，左指针指向的下标小于或等于 ii，右指针指向的下标大于或等于 jj。除非初始时左指针和右指针已经位于下标 ii 和 jj，否则一定是左指针先到达下标 ii 的位置或者右指针先到达下标 jj 的位置。
         *
         * 如果左指针先到达下标 ii 的位置，此时右指针还在下标 jj 的右侧，\text{sum}>\text{target}sum>target，因此一定是右指针左移，左指针不可能移到 ii 的右侧。
         *
         * 如果右指针先到达下标 jj 的位置，此时左指针还在下标 ii 的左侧，\text{sum}<\text{target}sum<target，因此一定是左指针右移，右指针不可能移到 jj 的左侧。
         *
         * 由此可见，在整个移动过程中，左指针不可能移到 ii 的右侧，右指针不可能移到 jj 的左侧，因此不会把可能的解过滤掉。
         *

         */
        int i=0,j=rightIndex;
       while (i< j){

            if (numbers[i]+numbers[j] > target){
                j--;
            }else if (numbers[i]+numbers[j] < target){
                i++;
            }else {
                return new int[]{i+1,j+1};
            }
        }

        return new int[]{-1, -1};

    }
    //辅助函数：帮助找找小于等于target的最大数值
    public int helper(int[] numbers, int target,int low,int high){

        if (low>high){
            return -1;
        }

        int mid = (low+high)/2;
        int value = numbers[mid];

        if (value > target){
            return helper(numbers,target,low,mid-1);

        }else if (value<target){
            return helper(numbers,target,mid+1,high);
        }else {
            return mid;
        }
    }
}
